package com.topView2;

import javax.swing.*;
import java.util.*;

/**
 * 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
 * <p>
 * 你返回所有和为 0 且不重复的三元组
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/3sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author: huangzhigao
 * @Date: 2023/2/11 17:31
 */
public class leecode15 {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        return findNSumTarget(nums, 3, 0, 0);
    }


    public List<List<Integer>> findNSumTarget(int[] nums, int n, int start, int target) {
        List<List<Integer>> res = new ArrayList<>();
        int size = nums.length;
        if (n < 2 || size < n) {
            return res;
        }
        if (n == 2) {
            //寻找两数之和
            int small = start;
            int big = size - 1;
            while (small < big) {
                int left = nums[small];
                int right = nums[big];
                int sum = left + right;
                if (sum == target) {
                    //相等情况，采集答案
                    res.add(new ArrayList<>(Arrays.asList(left, right)));
                    while (small < big && nums[small] == left) {
                        small++;
                    }
                    while (small < big && nums[big] == right) {
                        big--;
                    }
                } else if (sum > target) {
                    while (small < big && nums[big] == right) {
                        big--;
                    }
                } else if (sum < target) {
                    while (small < big && nums[small] == left) {
                        small++;
                    }
                }
            }
        } else {
            int i = start;
            while (i < size) {
                int now = nums[i];
                List<List<Integer>> subResult = findNSumTarget(nums, n - 1, i + 1, target - now);
                for (List<Integer> ele : subResult) {
                    ele.add(now);
                    res.add(ele);
                }
                while (i < size && nums[i] == now) {
                    i++;
                }
            }
        }
        return res;
    }


    public static void main(String[] args) {
        leecode15 leecode15 = new leecode15();
        leecode15.threeSum(new int[]{1, -1, -1, 0});
    }

}
